package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder3

/**
 * https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/description
 *
 * 题型： 二叉树的构建，二分法
 *
 * ```
 * 1008. 前序遍历构造二叉搜索树
 * 给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。
 * 保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。
 * 二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。
 * 二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。
 *
 * 示例 1：
 * 输入：preorder = [8,5,1,7,10,12]
 * 输出：[8,5,10,1,7,null,12]
 *
 * 示例 2:
 * 输入: preorder = [1,3]
 * 输出: [1,null,3]
 *
 * 提示：
 * 1 <= preorder.length <= 100
 * 1 <= preorder[i] <= 10^8
 * preorder 中的值 互不相同
 * ```
 */
class leetcode_1008 {
    @Test
    fun test_1() {
        val n1 = TreeNode(1)
        val n5 = TreeNode(5)
        val n7 = TreeNode(7)
        val n8 = TreeNode(8)
        val n10 = TreeNode(10)
        val n12 = TreeNode(12)

        val root = n8

        n8.left = n5
        n8.right = n10

        n5.left = n1
        n5.right = n7

        n10.right = n12

        val actual = bstFromPreorder(intArrayOf(8, 5, 1, 7, 10, 12))
        val expected: TreeNode = root
        Assert.assertEquals(printLevelOrder3(expected).toString(), printLevelOrder3(actual).toString())
    }

    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val n3 = TreeNode(3)

        val root = n1
        n1.right = n3

        val actual = bstFromPreorder(intArrayOf(1, 3))
        val expected: TreeNode = root
        Assert.assertEquals(printLevelOrder3(expected).toString(), printLevelOrder3(actual).toString())
    }


    private fun bstFromPreorder(preorder: IntArray): TreeNode? {
        /**
        题型： 二叉树的构建，二分法

        思路：
        https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/solutions/301677/javadai-ma-de-5chong-jie-ti-si-lu-by-sdwwld

        分称3中情况：
        情况 1 ： array 为空， 则返回 空 节点
        情况 2 ： array size 为1， 则把 第一个元素作为根节点返回
        情况 3 ： array size > 1
        第1步：第一个元素作为当前节点。
        第2步：找到比当前节点大的第一个数的index
        第3步：根据index，切割左右子树
        若index存在，左子树：[0, index), 右子树：[index, size)
        若index不存在，左子树：[0, size), 右子树：empty array
        递归左子树和右子树，它们的返回值作为节点的左节点和右节点
        返回当前节点

        空间复杂度：O(n)
        时间复杂度：O(n)
         */
        // 1 确定函数参数以及返回值

        // 2 确定终止条件
        if (preorder.size == 0) {
            return null
        }

        if (preorder.size == 1) {
            return TreeNode(preorder[0])
        }

        // 3 确定单层递归的处理逻辑
        // 1 找出当前节点
        val n: Int = preorder[0]
        val root: TreeNode = TreeNode(n)

        val preorder: IntArray = preorder.sliceArray(1 until preorder.size) // [1, size)

        // 2 找出第一个比 n 大的值 index
        var index: Int = -1
        for (i in 0 until preorder.size) {
            // TODO:大于，不是等于
            if (index == -1 && preorder[i] > n) {
                index = i
            }
        }
        // 3 根据index，切割出左右子树
        val leftArray: IntArray = if (index != -1) {
            preorder.sliceArray(0 until index) // [0, index)
        } else {
            preorder.sliceArray(0 until preorder.size) // [0.size)
        }

        val rightArray: IntArray = if (index != -1) {
            preorder.sliceArray(index until preorder.size)
            // [index2, size)
        } else {
            intArrayOf() // empty array
        }


        // 4 递归左右子树
        root.left = bstFromPreorder(leftArray)
        root.right = bstFromPreorder(rightArray)

        // 5 返回root
        return root
    }
}